#ifndef STX_ALGORITHM_STABLE_SORT_HPP
#define STX_ALGORITHM_STABLE_SORT_HPP

#include <stx/algorithm/common.hpp>
#include <stx/algorithm/sort.hpp>
#include <stx/algorithm/swap.hpp>
#include <stx/algorithm/inplace_merge.hpp>
#include <stx/core/scoped_ptr.hpp>

namespace stx {

template <class Compare, class InputIterator1, class InputIterator2>
inline void
merge_move_construct(
    InputIterator1 first1,
    InputIterator1 last1,
    InputIterator2 first2,
    InputIterator2 last2,
    typename std::iterator_traits<InputIterator1>::value_type* result,
    Compare comp)
{
    typedef typename std::iterator_traits<InputIterator1>::value_type value_type;
    destruct_n d(0);
    scoped_ptr<value_type, destruct_n&> h(result, d);
    for (; true; ++result) {
        if (first1 == last1) {
            for (; first2 != last2; ++first2, ++result, d.incr((value_type*)0)) {
                ::new (result) value_type(stx::move(*first2));
            }
            h.release();
            return;
        }
        if (first2 == last2) {
            for (; first1 != last1; ++first1, ++result, d.incr((value_type*)0)) {
                ::new (result) value_type(stx::move(*first1));
            }
            h.release();
            return;
        }
        if (comp(*first2, *first1)) {
            ::new (result) value_type(stx::move(*first2));
            d.incr((value_type*)0);
            ++first2;
        }
        else
        {
            ::new (result) value_type(stx::move(*first1));
            d.incr((value_type*)0);
            ++first1;
        }
    }
}

template <class Compare, class InputIterator1, class InputIterator2, class OutputIterator>
inline void
merge_move_assign(
    InputIterator1 first1,
    InputIterator1 last1,
    InputIterator2 first2,
    InputIterator2 last2,
    OutputIterator result,
    Compare comp)
{
    for (; first1 != last1; ++result) {
        if (first2 == last2) {
            for (; first1 != last1; ++first1, ++result) {
                *result = stx::move(*first1);
            }
            return;
        }
        if (comp(*first2, *first1)) {
            *result = stx::move(*first2);
            ++first2;
        } else {
            *result = stx::move(*first1);
            ++first1;
        }
    }
    for (; first2 != last2; ++first2, ++result) {
        *result = stx::move(*first2);
    }
}

template <class Compare, class RandomAccessIterator>
inline void
stable_sort_impl(
    RandomAccessIterator first,
    RandomAccessIterator last,
    Compare comp,
    typename std::iterator_traits<RandomAccessIterator>::difference_type len,
    typename std::iterator_traits<RandomAccessIterator>::value_type* buff,
    std::ptrdiff_t buff_size);

template <class Compare, class RandomAccessIterator>
inline void
stable_sort_move_impl(
    RandomAccessIterator first1,
    RandomAccessIterator last1,
    Compare comp,
    typename std::iterator_traits<RandomAccessIterator>::difference_type len,
    typename std::iterator_traits<RandomAccessIterator>::value_type* first2)
{
    typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
    switch (len) {
    case 0:
        return;
    case 1:
        ::new(first2) value_type(stx::move(*first1));
        return;
    case 2:
        destruct_n d(0);
        scoped_ptr<value_type, destruct_n&> h2(first2, d);
        if (comp(*--last1, *first1)) {
            ::new(first2) value_type(stx::move(*last1));
            d.incr((value_type*)0);
            ++first2;
            ::new(first2) value_type(stx::move(*first1));
        } else {
            ::new(first2) value_type(stx::move(*first1));
            d.incr((value_type*)0);
            ++first2;
            ::new(first2) value_type(stx::move(*last1));
        }
        h2.release();
        return;
    }
    if (len <= 8) {
        insertion_sort_move_impl<Compare>(first1, last1, first2, comp);
        return;
    }
    typename std::iterator_traits<RandomAccessIterator>::difference_type l2 = len / 2;
    RandomAccessIterator m = first1 + l2;
    stable_sort_impl<Compare>(first1, m, comp, l2, first2, l2);
    stable_sort_impl<Compare>(m, last1, comp, len - l2, first2 + l2, len - l2);
    merge_move_construct<Compare>(first1, m, m, last1, first2, comp);
}

template <class T>
struct stable_sort_impl_switch
{
    STX_STATIC_CONSTANT(unsigned, value, 128*is_trivially_copy_assignable<T>::value);
};

template <class Compare, class RandomAccessIterator>
inline void
stable_sort_impl(
    RandomAccessIterator first,
    RandomAccessIterator last,
    Compare comp,
    typename std::iterator_traits<RandomAccessIterator>::difference_type len,
    typename std::iterator_traits<RandomAccessIterator>::value_type* buff,
    std::ptrdiff_t buff_size)
{
    typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
    typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
    switch (len) {
    case 0:
    case 1:
        return;
    case 2:
        if (comp(*--last, *first)) {
            swap(*first, *last);
        }
        return;
    }
    if (len <= static_cast<difference_type>(stable_sort_impl_switch<value_type>::value)) {
        insertion_sort_impl<Compare>(first, last, comp);
        return;
    }
    typename std::iterator_traits<RandomAccessIterator>::difference_type l2 = len / 2;
    RandomAccessIterator m = first + l2;
    if (len <= buff_size) {
        destruct_n d(0);
        scoped_ptr<value_type, destruct_n&> h2(buff, d);
        stable_sort_move_impl<Compare>(first, m, comp, l2, buff);
        d.set(l2, (value_type*)0);
        stable_sort_move_impl<Compare>(m, last, comp, len - l2, buff + l2);
        d.set(len, (value_type*)0);
        merge_move_assign<Compare>(buff, buff + l2, buff + l2, buff + len, first, comp);
//         merge_impl<Compare>(
//             move_iterator<value_type*>(buff),
//             move_iterator<value_type*>(buff + l2),
//             move_iterator<RandomAccessIterator>(buff + l2),
//             move_iterator<RandomAccessIterator>(buff + len),
//             first,
//             comp);
        return;
    }
    stable_sort_impl<Compare>(first, m, comp, l2, buff, buff_size);
    stable_sort_impl<Compare>(m, last, comp, len - l2, buff, buff_size);
    inplace_merge_impl<Compare>(first, m, last, comp, l2, len - l2, buff, buff_size);
}

template <class RandomAccessIterator, class Compare>
inline void
stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
    typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
    difference_type len = last - first;
    std::pair<value_type*, std::ptrdiff_t> buf(0, 0);
    scoped_ptr<value_type, return_temporary_buffer_impl> h;
    if (len > static_cast<difference_type>(stable_sort_impl_switch<value_type>::value)) {
        buf = stx::get_temporary_buffer<value_type>(len);
        h.reset(buf.first);
    }
    typedef typename add_lvalue_reference<Compare>::type comp_ref;
    stable_sort_impl<comp_ref>(first, last, comp, len, buf.first, buf.second);
}

template <class RandomAccessIterator>
inline void
stable_sort(RandomAccessIterator first, RandomAccessIterator last)
{
    stx::stable_sort(first, last, stx::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
}

} // namespace stx

#endif // STX_ALGORITHM_STABLE_SORT_HPP
